package demo1;

import java.util.Deque;
import java.util.LinkedList;



public class Sort {
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end){
        if(start >= end){
            return;
        }
        if(end - start + 1 <= 15){
            inserSortRange(array,start,end);
            return;
        }
        //进行三数取中，寻找下标
        int index = threeMid(array,start,end);
        swap(array,start,end);
        int par = parttion(array,start,end);
        quick(array,start,par-1);
        quick(array, par+1, end);
    }

    private static void inserSortRange(int[] array, int start, int end) {
        for (int i = start+1; i < end; i++) {
            int tmp = array[i];
            int j = i-1;
            for ( ;j >= start;j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }else{
                    break;
                }
            }
            array[j] = tmp;
        }
    }

    private static int threeMid(int[] array, int start, int end) {
        int mid = (start + end)/2;
        if(array[start] < array[end]){
            if(array[start] > mid){
                return start;
            } else if (array[end] < mid) {
                return end;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[end]){
                return end;
            } else if (array[mid] > array[start]) {
                return start;
            } else{
                return mid;
            }
        }

    }


    //快速排序法
    private static int parttion(int[] array, int low, int high) {
        int pivot = array[low];
        int i =low;
        while(low < high){
            while(low < high && array[high] >= pivot){
                high--;
            }
            while(low < high && array[low] <= pivot){
                low++;
            }
            swap(array,low,high);
        }
        swap(array,i,low);
        return low;
    }
    private static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    //快速排序挖坑法
    private static int parttion1(int[] array, int low, int high) {

        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            array[low] = array[high];
            while(low < high && array[low] <= tmp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }

    public static void quickSortNor(int[] array){
        int start = 0;
        int end = array.length - 1;
        int par = parttion(array,start,end);
        Deque<Integer> stack = new LinkedList<>();
        if(par > start){
            stack.push(start);
            stack.push(par-1);
        }
        if(par < end-1){
            stack.push(par+1);
            stack.push(end);
        }
        while(!stack.isEmpty()){
            end = stack.poll();
            start = stack.poll();
            par = parttion1(array,start,end);
            if(par > start){
                stack.push(start);
                stack.push(par-1);
            }
            if(par < end-1){
                stack.push(par+1);
                stack.push(end);
            }
        }
    }

    public static void mergeSort(int[] arrray){
        mergeSortChild(arrray,0,arrray.length-1);
    }

    private static void mergeSortChild(int[] array,int left,int right){
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;
        mergeSortChild(array,left,mid);

        mergeSortChild(array,mid+1,array.length-1);

        //合并
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int s2 = mid+1;
        int e1 = mid;
        int e2 = right;
        while(s1 <= e1 && s2 <= e2){
            if(array[s1] <= array[s2]){
                tmp[k++] = array[s1++];
            }else{
                tmp[k] = array[s2];
                k++;
                s2++;
            }
        }
        while(s1 <= e1){
            tmp[k++] = array[s1++];
        }
        while(s2 <= e2){
            tmp[k++] = array[s2++];
        }
    }
}
